package leetcode.剑指offer.前40;

import org.junit.Test;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/30 9:45
 * @description :
 */
public class 剑指_33_二叉搜索树的后序遍历序列 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.verifyPostorder(new int[]{1,3,2,6,5}));
    }

    class Solution {
        public boolean verifyPostorder(int[] postorder) {
            return recur(postorder, 0, postorder.length - 1);
        }

        private boolean recur(int[] postorder, int i, int j) {
            if (i >= j) return true;
            int p = i;
            while (postorder[p] < postorder[j]) p++;
            int m = p;
            while (postorder[p] > postorder[j]) p++;
            return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
        }
    }


}
